{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of K-Divisible Components"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxKDivisibleComponents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #可以被 K 整除连通块的最大数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵 <code>n</code>&nbsp;个节点的无向树，节点编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;。给你整数&nbsp;<code>n</code>&nbsp;和一个长度为 <code>n - 1</code>&nbsp;的二维整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;表示树中节点&nbsp;<code>a<sub>i</sub></code> 和&nbsp;<code>b<sub>i</sub></code>&nbsp;有一条边。</p>\n",
    "\n",
    "<p>同时给你一个下标从 <strong>0</strong>&nbsp;开始长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>values</code>&nbsp;，其中&nbsp;<code>values[i]</code>&nbsp;是第 <code>i</code>&nbsp;个节点的 <strong>值</strong>&nbsp;。再给你一个整数&nbsp;<code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>你可以从树中删除一些边，也可以一条边也不删，得到若干连通块。一个 <strong>连通块的值</strong> 定义为连通块中所有节点值之和。如果所有连通块的值都可以被 <code>k</code>&nbsp;整除，那么我们说这是一个 <strong>合法分割</strong>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回所有合法分割中，<b>连通块数目的最大值</b>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/08/07/example12-cropped2svg.jpg\" style=\"width: 1024px; height: 453px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 5, edges = [[0,2],[1,2],[1,3],[2,4]], values = [1,8,1,4,4], k = 6\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>我们删除节点 1 和 2 之间的边。这是一个合法分割，因为：\n",
    "- 节点 1 和 3 所在连通块的值为 values[1] + values[3] = 12 。\n",
    "- 节点 0 ，2 和 4 所在连通块的值为 values[0] + values[2] + values[4] = 6 。\n",
    "最多可以得到 2 个连通块的合法分割。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/08/07/example21svg-1.jpg\" style=\"width: 999px; height: 338px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 7, edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values = [3,0,6,1,5,2,1], k = 3\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>我们删除节点 0 和 2 ，以及节点 0 和 1 之间的边。这是一个合法分割，因为：\n",
    "- 节点 0 的连通块的值为 values[0] = 3 。\n",
    "- 节点 2 ，5 和 6 所在连通块的值为 values[2] + values[5] + values[6] = 9 。\n",
    "- 节点 1 ，3 和 4 的连通块的值为 values[1] + values[3] + values[4] = 6 。\n",
    "最多可以得到 3 个连通块的合法分割。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>values.length == n</code></li>\n",
    "\t<li><code>0 &lt;= values[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>values</code>&nbsp;之和可以被 <code>k</code>&nbsp;整除。</li>\n",
    "\t<li>输入保证&nbsp;<code>edges</code>&nbsp;是一棵无向树。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-k-divisible-components](https://leetcode.cn/problems/maximum-number-of-k-divisible-components/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-k-divisible-components](https://leetcode.cn/problems/maximum-number-of-k-divisible-components/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[0,2],[1,2],[1,3],[2,4]]\\n[1,8,1,4,4]\\n6', '7\\n[[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]\\n[3,0,6,1,5,2,1]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        vs = values[:]\n",
    "        ds = [0 for i in range(n)]\n",
    "        es = [[] for i in range(n)]\n",
    "        for a,b in edges:\n",
    "            ds[a] += 1\n",
    "            ds[b] += 1\n",
    "            es[a].append(b)\n",
    "            es[b].append(a)\n",
    "        h = []\n",
    "        out = [False for i in range(n)]\n",
    "        for i in range(n):\n",
    "            if ds[i] == 1:\n",
    "                h.append(i)\n",
    "                out[i] = True\n",
    "        res = 1\n",
    "        # print(h)\n",
    "        while len(h) != 0:\n",
    "            id = h.pop()\n",
    "            # print(id)\n",
    "            rnid = -1\n",
    "            for nid in es[id]:\n",
    "                ds[nid] -= 1\n",
    "                if not out[nid]:\n",
    "                    rnid = nid\n",
    "            if rnid == -1:\n",
    "                break\n",
    "            # print(\"rnid\", rnid)\n",
    "            \n",
    "            if ds[rnid] == 1:\n",
    "                out[rnid] = True\n",
    "                if vs[id] % k == 0:\n",
    "                    res += 1\n",
    "                    h.append(rnid)\n",
    "                else:\n",
    "                    vs[rnid] += vs[id]\n",
    "                    h.append(rnid)      \n",
    "            else:\n",
    "                if vs[id] % k == 0:\n",
    "                    res += 1\n",
    "                else:\n",
    "                    vs[rnid] += vs[id] \n",
    "        if len(h) != 0 and vs[h[0]] % k == 0:\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        q = []\n",
    "        vi = [False] * n\n",
    "        g = [[] for _ in range(n)]\n",
    "        ind = [0 for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "            ind[a] += 1\n",
    "            ind[b] += 1\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if not vi[i] and ind[i] <= 1:\n",
    "                vi[i] = True\n",
    "                q.append(i)\n",
    "        while len(q):\n",
    "            nq = []\n",
    "            while len(q):\n",
    "                i = q.pop()\n",
    "                if values[i] % k == 0:\n",
    "                    res += 1\n",
    "                for ne in g[i]:\n",
    "                    values[ne] += values[i]\n",
    "                    ind[ne] -= 1\n",
    "                    if not vi[ne] and ind[ne] <= 1:\n",
    "                        vi[ne] = True\n",
    "                        nq.append(ne)\n",
    "            q = nq\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        adj = [list() for _ in range(n)]\n",
    "        visit = [False] * n\n",
    "        degree = [0] * n\n",
    "        for a, b in edges:\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "            degree[a] += 1\n",
    "            degree[b] += 1\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if degree[i] <= 1:\n",
    "                q.append(i)\n",
    "                visit[i] = True\n",
    "        ans = 0\n",
    "        while q:\n",
    "            t = deque()\n",
    "            while q:\n",
    "                front = q.popleft()\n",
    "                if values[front] % k == 0:\n",
    "                    ans += 1\n",
    "                for v in adj[front]:\n",
    "                    values[v] += values[front] % k\n",
    "                    values[v] %= k\n",
    "                    if visit[v]:\n",
    "                        continue\n",
    "                    degree[v] -= 1\n",
    "                    if degree[v] <= 1:\n",
    "                        visit[v] = True\n",
    "                        t.append(v)\n",
    "            q = t\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        bk = 0\n",
    "\n",
    "        c_c = [0] * n\n",
    "        c_l = [[] for _ in range(n)]\n",
    "\n",
    "        for i, j in edges:\n",
    "            c_c[i] += 1\n",
    "            c_c[j] += 1\n",
    "            c_l[i].append(j)\n",
    "            c_l[j].append(i)\n",
    "\n",
    "        q = collections.deque()\n",
    "        q = [i for i in range(n) if c_c[i] == 1]\n",
    "\n",
    "        while q:\n",
    "            curr = q.pop()\n",
    "\n",
    "            c_c[curr] -= 1\n",
    "\n",
    "            # 这一步很关键\n",
    "            if not c_l[curr]:\n",
    "                continue\n",
    "\n",
    "            t = c_l[curr].pop()\n",
    "            c_l[t] = [no for no in c_l[t] if no != curr]\n",
    "            c_c[t] -= 1\n",
    "            if c_c[t] == 1:\n",
    "                q.append(t)\n",
    "\n",
    "            if not values[curr] % k:\n",
    "                bk += 1\n",
    "            else:\n",
    "                values[t] += values[curr]\n",
    "\n",
    "        return bk + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], kv: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        if not edges:\n",
    "            return 1\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        l = []\n",
    "        for k in g:\n",
    "            if  len(g[k]) == 1:\n",
    "                l.append(k)\n",
    "        \n",
    "        ans = 0\n",
    "        while True:\n",
    "            ll = []\n",
    "            #print(l)\n",
    "            for e in l:\n",
    "                if len(g[e]) == 0:\n",
    "                    return ans + 1\n",
    "                p = g[e][0]\n",
    "                if values[e] % kv == 0:\n",
    "                    #print(values[e],e)\n",
    "                    ans+=1\n",
    "                else:\n",
    "                    values[p]+=values[e]\n",
    "                \n",
    "                g[p].remove(e)\n",
    "                if len(g[p]) == 1:\n",
    "                    ll.append(p)\n",
    "            l = ll \n",
    "        return ans \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        g = defaultdict(list)\n",
    "        for i, j in edges:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "            \n",
    "        d = {}\n",
    "        for i, j in g.items():\n",
    "            d[i] = len(j)\n",
    "        \n",
    "        s = set([i for i in d if d[i] == 1])\n",
    "        \n",
    "        res = 0\n",
    "        \n",
    "        while s:\n",
    "            # print(s)\n",
    "            ns = set()\n",
    "            for i in s:\n",
    "                if values[i] % k == 0:\n",
    "                    res += 1\n",
    "                    values[i] = 0\n",
    "                \n",
    "                for j in g[i]:\n",
    "                    if d[j]:\n",
    "                        d[j] -= 1\n",
    "                        values[j] += values[i]\n",
    "                    if d[j] == 1 and j not in s:\n",
    "                        ns.add(j)\n",
    "                values[i] = 0\n",
    "                d[i] = 0\n",
    "            s = ns\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        if n ==1:return 1\n",
    "        #不断的合并节点\n",
    "        #度为1的节点如果不是K的倍数，则合并到邻居上\n",
    "        #迭代过程\n",
    "\n",
    "        degree = [0]*n\n",
    "        g = [ set() for _ in range(n)]\n",
    "        for i,j in edges:\n",
    "            degree[i] += 1\n",
    "            degree[j] += 1\n",
    "            g[i].add(j)\n",
    "            g[j].add(i)\n",
    "        \n",
    "        q = deque()\n",
    "        ans = 0\n",
    "        inq = [False]*n\n",
    "        for i in range(n):\n",
    "            if degree[i] == 1:\n",
    "                q.append(i)\n",
    "                inq[i] = True\n",
    "        \n",
    "        while q:\n",
    "            \n",
    "            top = q.popleft() \n",
    "            # print(degree,g,top)\n",
    "            if degree[top]==0:  \n",
    "                continue \n",
    "\n",
    "            neib = g[top].pop()\n",
    "            degree[top] -= 1\n",
    "            g[ neib ].remove(top)\n",
    "            degree[neib]-=1\n",
    "            if values[top] % k == 0: \n",
    "                ans += 1 \n",
    "            else: \n",
    "                values[neib]+=values[top] \n",
    "\n",
    "            if degree[neib]==0:  \n",
    "                ans += 1\n",
    "            if degree[neib]==1 :\n",
    "                q.append(neib)\n",
    "                # inq[neib] = True\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "\n",
    "        # 记录每个点的边\n",
    "        l_pe = [set() for _ in range(n)]\n",
    "\n",
    "        for u, v in edges:\n",
    "            l_pe[u].add(v)\n",
    "            l_pe[v].add(u)\n",
    "\n",
    "        # 从边为1的点开始\n",
    "        dp = [i for i, e in enumerate(l_pe) if len(e) == 1]\n",
    "\n",
    "        ret = 0\n",
    "\n",
    "        while dp:\n",
    "            u = dp.pop(0)\n",
    "            if values[u] % k == 0:\n",
    "                ret += 1\n",
    "                values[u] = 0\n",
    "\n",
    "            for v in l_pe[u]:\n",
    "                values[v] += values[u]\n",
    "                l_pe[v].remove(u)\n",
    "                if len(l_pe[v]) == 1:\n",
    "                    dp.append(v)\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        con = [set() for i in range(n)]\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        for i, j in edges:\n",
    "            con[i].add(j)\n",
    "            con[j].add(i)\n",
    "        test = []\n",
    "        for i in range(n):\n",
    "            if len(con[i]) == 1:\n",
    "                test.append(i)\n",
    "        while test:\n",
    "            x = test.pop()\n",
    "            if values[x] % k == 0:\n",
    "                ans += 1\n",
    "                for j in con[x]:\n",
    "                    con[j].remove(x)\n",
    "                    if len(con[j]) == 1:\n",
    "                        test.append(j)\n",
    "            else:\n",
    "                for j in con[x]:\n",
    "                    con[j].remove(x)\n",
    "                    values[j] += values[x]\n",
    "                    if len(con[j]) == 1:\n",
    "                        test.append(j)\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        neighbour = collections.defaultdict(set)\n",
    "        for a, b in edges :\n",
    "            neighbour[a].add(b)\n",
    "            neighbour[b].add(a)\n",
    "        if n == 1 :\n",
    "            return 1\n",
    "        \n",
    "        leaf = set([t for t in neighbour if len(neighbour[t])==1])\n",
    "        to_ret = 0\n",
    "        while len(leaf) :\n",
    "            node = leaf.pop()\n",
    "            if values[node] % k == 0 :\n",
    "                to_ret += 1\n",
    "                for t in neighbour[node] :\n",
    "                    neighbour[t].remove(node)\n",
    "                    if len(neighbour[t]) == 1 :\n",
    "                        leaf.add(t)\n",
    "            else :\n",
    "                for t in neighbour[node] :\n",
    "                    neighbour[t].remove(node)\n",
    "                    values[t] += values[node]\n",
    "                    if len(neighbour[t]) == 1 :\n",
    "                        leaf.add(t)\n",
    "        return to_ret\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        subtree_sums = values[:]\n",
    "        g=defaultdict(set)\n",
    "        for x,y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        leafs = {i for i in range(n) if len(g[i])==1}\n",
    "        ans=1\n",
    "        while leafs:\n",
    "            x=leafs.pop()\n",
    "            if subtree_sums[x]%k==0:\n",
    "                ans+=1\n",
    "\n",
    "            y=g[x].pop()\n",
    "            g[y].remove(x)\n",
    "            subtree_sums[y]+=subtree_sums[x]\n",
    "\n",
    "            if len(g[y])==0:\n",
    "                leafs.remove(y)\n",
    "            elif len(g[y])==1:\n",
    "                leafs.add(y)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        if n== 1:\n",
    "            return 1\n",
    "        d = Counter()\n",
    "        g = defaultdict(set)\n",
    "        \n",
    "        for a,b in edges:\n",
    "            d[a] += 1\n",
    "            d[b] += 1\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        \n",
    "        q = deque()\n",
    "        for node in d:\n",
    "            if d[node] == 1:\n",
    "                q.append(node)\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            l = deque()\n",
    "            for node in q:\n",
    "                if values[node]%k == 0:\n",
    "                    cnt += 1\n",
    "                for nei in g[node]:\n",
    "                    d[nei] -= 1\n",
    "                    values[nei] += values[node]\n",
    "                    if d[nei] == 1:\n",
    "                        l.append(nei)\n",
    "            \n",
    "            q = l\n",
    "        \n",
    "        return cnt\n",
    "                    \n",
    "                \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        if values is None or len(values) == 0:\n",
    "            return 0\n",
    "        \n",
    "        total = sum(values)\n",
    "        if total % k > 0:\n",
    "            return 0\n",
    "        \n",
    "        if n == 1:\n",
    "            return 1\n",
    "        \n",
    "        info = {}\n",
    "        for x, y in edges:\n",
    "            if info.get(x, None) is None:\n",
    "                info[x] = set()\n",
    "            info[x].add(y)\n",
    "            if info.get(y, None) is None:\n",
    "                info[y] = set()\n",
    "            info[y].add(x)\n",
    "        \n",
    "        info_val = {}\n",
    "        for i in range(n):\n",
    "            info_val[i] = values[i]\n",
    "        \n",
    "\n",
    "        opts = []\n",
    "        tmp_opts = None\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if len(info[i]) == 1:\n",
    "                cnt += 1\n",
    "                opts.append(i)\n",
    "        \n",
    "        res = 0\n",
    "        while cnt < n and opts:\n",
    "            tmp_opts = []\n",
    "            for i in opts:\n",
    "                # print(i, info)\n",
    "                j = info[i].pop()\n",
    "                if info_val[i] % k == 0:\n",
    "                    res += 1\n",
    "                else:\n",
    "                    info_val[j] += info_val[i]\n",
    "                info[j].remove(i)\n",
    "                if len(info[j]) == 1:\n",
    "                    cnt += 1\n",
    "                    tmp_opts.append(j)\n",
    "            opts = tmp_opts\n",
    "            # print(res, opts, cnt)\n",
    "            if cnt == n:\n",
    "                break\n",
    "        \n",
    "        # for i in opts:\n",
    "        #     if info_val[i] % k == 0:\n",
    "        #         res += 1\n",
    "        # res += len(opts)\n",
    "        flag = False\n",
    "        for i in opts:\n",
    "            if info_val[i] % k == 0:\n",
    "                flag = True\n",
    "                res += 1\n",
    "        \n",
    "        if not flag:\n",
    "            res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        dq1 = deque(x for x in range(n) if len(g[x]) == 1)\n",
    "        ans = set()  # 删除边的集合\n",
    "        while dq1:\n",
    "            x = dq1.popleft()\n",
    "            if len(g[x]) == 0: continue\n",
    "            if values[x] % k == 0:\n",
    "                y = g[x].pop()\n",
    "                g[y].remove(x)\n",
    "                # 删除 (x, y)\n",
    "                if x < y: ans.add((x, y))\n",
    "                else: ans.add((y, x))\n",
    "                if len(g[y]) == 1:\n",
    "                    dq1.append(y)\n",
    "                continue\n",
    "            y = g[x].pop()\n",
    "            g[y].remove(x)\n",
    "            values[y] += values[x]  # 把x上的值累加到y上\n",
    "            if len(g[y]) == 1:\n",
    "                dq1.append(y)\n",
    "        return len(ans) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        res=0\n",
    "        adj=collections.defaultdict(set)\n",
    "        for a,b in edges:\n",
    "            adj[a].add(b)\n",
    "            adj[b].add(a)\n",
    "        all_node=set(range(n))\n",
    "        while all_node:\n",
    "            del_node=set()\n",
    "            for node in all_node:\n",
    "                if len(adj[node])<2:\n",
    "                    del_node.add(node)\n",
    "                    if values[node]%k==0:\n",
    "                        res+=1\n",
    "                        values[node]=0\n",
    "                    if adj[node]:\n",
    "                        node_adj=adj[node].pop()\n",
    "                        adj[node_adj].discard(node)\n",
    "                        values[node_adj]+=values[node]\n",
    "            all_node-=del_node\n",
    "        return res\n",
    "                    \n",
    "                    \n",
    "                        \n",
    "                        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, idx, v):\n",
    "        self.idx = idx\n",
    "        self.fr = -1\n",
    "        self.child = []\n",
    "        self.seen_child_cnt = 0\n",
    "        self.v = v\n",
    "\n",
    "        self.total_v = self.v\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        node_list = [Node(i, values[i]) for i in range(n)]\n",
    "        graph = {}\n",
    "        for a, b in edges:\n",
    "            if a not in graph:\n",
    "                graph[a] = []\n",
    "            if b not in graph:\n",
    "                graph[b] = []\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "\n",
    "        q = [node_list[0]]\n",
    "        seen = [0] * n\n",
    "        seen[0] = 1\n",
    "        while q:\n",
    "            node = q.pop()\n",
    "            for nxt in graph[node.idx]:\n",
    "                if not seen[nxt]:\n",
    "                    q.append(node_list[nxt])\n",
    "                    seen[nxt] = 1\n",
    "                    node.child.append(nxt)\n",
    "                    node_list[nxt].fr = node.idx\n",
    "\n",
    "        # all leaf\n",
    "        leaf_nodes = []\n",
    "        for i in range(n):\n",
    "            if not node_list[i].child:\n",
    "                leaf_nodes.append(node_list[i])\n",
    "        res = 0\n",
    "        while leaf_nodes:\n",
    "            node = leaf_nodes.pop()\n",
    "            if node.total_v % k == 0:\n",
    "                res += 1\n",
    "                if node.fr != -1:\n",
    "                    fr_node = node_list[node.fr]\n",
    "                    fr_node.seen_child_cnt += 1\n",
    "                    if fr_node.seen_child_cnt == len(fr_node.child):\n",
    "                        leaf_nodes.append(fr_node)\n",
    "            else:\n",
    "                fr_node = node_list[node.fr]\n",
    "                fr_node.total_v += node.total_v\n",
    "                fr_node.seen_child_cnt += 1\n",
    "                if fr_node.seen_child_cnt == len(fr_node.child):\n",
    "                    leaf_nodes.append(fr_node)\n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, e: List[List[int]], v: List[int], kk: int) -> int:\n",
    "        if n==1:\n",
    "            return 1 \n",
    "        v = [(j%kk) for j in v ]\n",
    "        v = {j:v[j] for j in range(len(v))}\n",
    "        ans = 0\n",
    "        g = defaultdict(set) \n",
    "        d = defaultdict(int)\n",
    "        for x, y in e:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "            d[x]+=1\n",
    "            d[y]+=1 \n",
    "        s = [j for j in d if d[j]==1]\n",
    "        vis = set(s)\n",
    "        while s:\n",
    "            tmp = []\n",
    "            for j in s:\n",
    "                vis.add(j)\n",
    "                if v[j]%kk==0:\n",
    "                    ans+=1 \n",
    "                for k in g[j]:\n",
    "                    if k not in vis:\n",
    "                        d[k]-=1 \n",
    "                        v[k]+=v[j]\n",
    "                        if d[k]==1:\n",
    "                            tmp.append(k)\n",
    "            s = tmp\n",
    "        return ans \n",
    "                \n",
    "#                     vis.add(j) \n",
    "#                     jj = list(g[j])[0]\n",
    "#                     g[jj].remove(j)\n",
    "#                     if d[jj]\n",
    "#                     del g[j] \n",
    "#                 else:\n",
    "#                     vis.add(j)\n",
    "#                     jj=list(g[j])[0]\n",
    "#                     g[jj].remove(j)\n",
    "#                     del g[j]\n",
    "                    \n",
    "                    \n",
    "#         for j in s:\n",
    "#             if v[j]==0:\n",
    "#                 ans+=1 \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        dp={}       \n",
    "        neibers=[set() for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            neibers[edge[0]].add(edge[1])\n",
    "            neibers[edge[1]].add(edge[0])\n",
    "        res=1\n",
    "        def dfs(visited,node):\n",
    "            visited.add(node)\n",
    "            res=values[node]\n",
    "            for neiber in neibers[node]:\n",
    "                if neiber not in visited:\n",
    "                    if (node,neiber) in dp:\n",
    "                        res+=dp[(node,neiber)]\n",
    "                    else:\n",
    "                        dp[(node,neiber)]=dfs(visited,neiber)\n",
    "                        res+=dp[(node,neiber)]\n",
    "            return res\n",
    "        # 找到一个可以删的边res+1\n",
    "        for edge in edges:\n",
    "            neibers[edge[0]].remove(edge[1])\n",
    "            neibers[edge[1]].remove(edge[0])\n",
    "            if dfs(set(),edge[0])%k==0 and dfs(set(),edge[1])%k==0:\n",
    "                res+=1\n",
    "            neibers[edge[0]].add(edge[1])\n",
    "            neibers[edge[1]].add(edge[0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        \n",
    "        if not edges:\n",
    "            return 1\n",
    "        g = defaultdict(list)\n",
    "        d = defaultdict(int)\n",
    "        \n",
    "        for edge in edges:\n",
    "            a, b = edge\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "            d[a] += 1\n",
    "            d[b] += 1\n",
    "        \n",
    "        q = []\n",
    "        ans = 0\n",
    "        \n",
    "        d2 = dict(d)\n",
    "        \n",
    "        vis = set()\n",
    "        for i in range(n):\n",
    "            if d[i] == 1:\n",
    "                q.append(i)\n",
    "                vis.add(i)\n",
    "        \n",
    "        root = -1\n",
    "        while q:\n",
    "            len_ = len(q)\n",
    "            for _ in range(len_):\n",
    "                c = q.pop(0)\n",
    "                for v in g[c]:\n",
    "                    d[v] -= 1\n",
    "                    if d[v] == 1 and v not in vis:\n",
    "                        q.append(v)\n",
    "                        vis.add(v)\n",
    "                    \n",
    "                    if d[v] == 0:\n",
    "                        root = v\n",
    "        \n",
    "        ss = [0] * n\n",
    "        def scores(node: int, p: int) -> int:\n",
    "            \n",
    "            res = 0\n",
    "            res += values[node]\n",
    "            \n",
    "            for v in g[node]:\n",
    "                if v != p:\n",
    "                    res += scores(v, node)\n",
    "            \n",
    "            ss[node] = res\n",
    "            return res\n",
    "        \n",
    "        scores(root, -1)\n",
    "        \n",
    "        \n",
    "        q = []\n",
    "        vis = set()\n",
    "        for i in range(n):\n",
    "            if d2[i] == 1:\n",
    "                q.append(i)\n",
    "                vis.add(i)\n",
    "        \n",
    "        while q:\n",
    "            len_ = len(q)\n",
    "            \n",
    "            for _ in range(len_):\n",
    "                c = q.pop(0)\n",
    "                if ss[c] % k == 0:\n",
    "                    ans += 1\n",
    "                for v in g[c]:\n",
    "                    d2[v] -= 1\n",
    "                    if d2[v] == 1 and v not in vis:\n",
    "                        q.append(v)\n",
    "                        vis.add(v)\n",
    "        \n",
    "        \n",
    "        return ans\n",
    "                    \n",
    "        \n",
    "        \n",
    "        \n",
    "            \n",
    "        \n",
    "        \n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "res = 0\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, idx, fa):\n",
    "        su = self.values[idx]\n",
    "        for neighbor in self.neighbors[idx]:\n",
    "            if neighbor == fa:\n",
    "                continue\n",
    "            s = self.dfs(neighbor, idx)\n",
    "            su += s\n",
    "            if s % self.k == 0:\n",
    "                self.res += 1\n",
    "        return su\n",
    "    \n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        self.k = k\n",
    "        self.values = values\n",
    "        self.neighbors = [[] for i in range(n)]\n",
    "        for a, b in edges:\n",
    "            self.neighbors[a].append(b)\n",
    "            self.neighbors[b].append(a)\n",
    "        self.res = 1\n",
    "        self.dfs(0, -1)\n",
    "        return self.res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,u,p):\n",
    "        self.s[u] = self.vals[u]\n",
    "        for v in self.g[u]:\n",
    "            if v == p:\n",
    "                continue\n",
    "            self.s[u] += self.dfs(v, u)\n",
    "        return self.s[u]\n",
    "        \n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        self.g = [[] for _ in range(n)]\n",
    "        self.s = [0] * n\n",
    "        self.vals = values\n",
    "        self.k = k\n",
    "        for u,v in edges:\n",
    "            self.g[u].append(v)\n",
    "            self.g[v].append(u)\n",
    "        self.dfs(0,-1)\n",
    "        res = 0\n",
    "\n",
    "        for u in range(n):\n",
    "            if self.s[u] % k == 0:\n",
    "                res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ans = 0\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        mp = [[] for i in range(n)]\n",
    "        for i in edges:\n",
    "            mp[i[0]].append(i[1])\n",
    "            mp[i[1]].append(i[0])\n",
    "        global ans\n",
    "        ans = 0\n",
    "        def dfs(fr,loc):\n",
    "            tmp = values[loc]\n",
    "            for i in mp[loc]:\n",
    "                if i != fr:\n",
    "                    tmp += dfs(loc,i)\n",
    "            if tmp % k == 0:\n",
    "                global ans\n",
    "                ans += 1\n",
    "                return 0\n",
    "            return tmp\n",
    "        dfs(-1,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        g = [[] for _ in range(n)]    \n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        ans = 0\n",
    "        def dfs(root, pa):\n",
    "            nonlocal ans\n",
    "            res = values[root]%k\n",
    "            for node in g[root]:\n",
    "                if node != pa:\n",
    "                    res += dfs(node, root)\n",
    "            if res % k == 0:\n",
    "                ans += 1\n",
    "            return res % k\n",
    "        dfs(0, -1)\n",
    "        return ans\n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "什么样的边可以被分割？\n",
    "子树连通块的值为k的倍数\n",
    "\n",
    "从任意一点出发的答案都是一样的吗？\n",
    "考虑边 要么是u->v,要么是v->u，如果u可以是个合法连通块，那么v肯定也是，所以没有区别。\n",
    "'''\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        def dfs(x:int,fa:int):\n",
    "            cntx=0\n",
    "            valx=values[x]\n",
    "            for y in g[x]:\n",
    "                if y==fa:continue  \n",
    "                cnt,val=dfs(y,x) #子树中所有节点和，以及分割连通块数目\n",
    "                cntx+=cnt\n",
    "                valx+=val\n",
    "                if val %k==0:\n",
    "                    cntx+=1\n",
    "            return (cntx,valx)\n",
    "        return (dfs(0,-1)[0]+1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        ans = 0\n",
    "        def dfs(x, p):\n",
    "            nonlocal ans\n",
    "            c = values[x]\n",
    "            for b in graph[x]:\n",
    "                if b != p:\n",
    "                    c += dfs(b, x)\n",
    "            c %= k\n",
    "            ans += (c == 0)\n",
    "            return c\n",
    "        dfs(0, None)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], vals: List[int], k: int) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        table = [0] * n\n",
    "        self.dfs(graph, vals, 0, -1, table)\n",
    "        from collections import deque\n",
    "        self.queue = deque([[0, -1]])\n",
    "        self.res = 0\n",
    "        while self.queue:\n",
    "            node, parent = self.queue.popleft()\n",
    "            self.dfs2(graph, node, parent, table, k)\n",
    "            self.res += 1\n",
    "        return self.res\n",
    "        \n",
    "    def dfs(self, graph, vals, node, parent, table):\n",
    "        res = vals[node]\n",
    "        for anode in graph[node]:\n",
    "            if anode != parent:\n",
    "                res += self.dfs(graph, vals, anode, node, table)\n",
    "        table[node] = res\n",
    "        return res\n",
    "    \n",
    "    def dfs2(self, graph, node, parent, table, k):\n",
    "        for anode in graph[node]:\n",
    "            if anode != parent:\n",
    "                if table[anode] % k == 0:\n",
    "                    self.queue.append([anode, node])\n",
    "                else:\n",
    "                    self.dfs2(graph, anode, node, table, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        group = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            group[x].append(y)\n",
    "            group[y].append(x)\n",
    "\n",
    "        def dfs(node, fa):\n",
    "            s = values[node]\n",
    "            for i in group[node]:\n",
    "                if i != fa:\n",
    "                    s += dfs(i, node)\n",
    "            nonlocal ans\n",
    "            ans += s % k == 0\n",
    "            return s\n",
    "        ans = 0\n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        # 子树和如果是k的倍数说明这个部分可以切掉\n",
    "        g = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        ans = 0\n",
    "        def dfs(cur, pa):\n",
    "            s = values[cur]\n",
    "            for nxt in g[cur]:\n",
    "                if nxt != pa:\n",
    "                    s += dfs(nxt, cur)\n",
    "            nonlocal ans\n",
    "            if s % k == 0:\n",
    "                ans += 1\n",
    "            return s\n",
    "        dfs(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        \n",
    "        print(graph)\n",
    "        def DFS(root, parent):\n",
    "  \n",
    "            \n",
    "            val = values[root]\n",
    "            total = 0\n",
    "            for node in graph[root]:\n",
    "                if node==parent:\n",
    "                    continue \n",
    "                num, x = DFS(node, root)\n",
    "                total += num \n",
    "                val += x \n",
    "            \n",
    "            if val%k==0:\n",
    "                return total+1,0\n",
    "            else:\n",
    "                return total, val \n",
    "        \n",
    "        total, val = DFS(0,-1)\n",
    "        print(total, val)\n",
    "        if val==0:\n",
    "            return total\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param edges:\n",
    "        :param values:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        total = sum(values)\n",
    "\n",
    "        m1 = defaultdict(list)\n",
    "        for i in edges:\n",
    "            m1[i[0]].append(i[1])\n",
    "            m1[i[1]].append(i[0])\n",
    "\n",
    "        st = 0\n",
    "        map_total = defaultdict(int)\n",
    "\n",
    "        def iter(node, prev = -1):\n",
    "            curv = values[node]\n",
    "            for i in m1[node]:\n",
    "                if i != prev:\n",
    "                    curv += iter(i, node)\n",
    "            map_total[node] = curv\n",
    "            return curv\n",
    "\n",
    "        iter(0)\n",
    "        cnt = 0\n",
    "        for i in map_total:\n",
    "            if map_total[i] % k ==0:\n",
    "                cnt += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        cnt = values.copy()\n",
    "        g = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        def dfs(v , fa):\n",
    "            for x in g[v]:\n",
    "                if x != fa:\n",
    "                    dfs(x, v)\n",
    "                    cnt[v] += cnt[x]\n",
    "        dfs(0, -1)\n",
    "        ans = 1\n",
    "        # print(cnt)\n",
    "        def dfs1(v, fa, tot):\n",
    "            for x in g[v]:\n",
    "                if x != fa:\n",
    "                    if cnt[x] % k == 0:\n",
    "                        nonlocal ans\n",
    "                        ans += 1\n",
    "                        tot -= cnt[x]\n",
    "                        dfs1(x, v, cnt[x])\n",
    "                    else:\n",
    "                        dfs1(x, v, tot)\n",
    "                        \n",
    "        dfs1(0, -1, cnt[0])\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        \n",
    "        print(graph)\n",
    "        def DFS(root, parent):\n",
    "  \n",
    "            \n",
    "            val = values[root]\n",
    "            total = 0\n",
    "            for node in graph[root]:\n",
    "                if node==parent:\n",
    "                    continue \n",
    "                num, x = DFS(node, root)\n",
    "                total += num \n",
    "                val += x \n",
    "            \n",
    "            if val%k==0:\n",
    "                return total+1,0\n",
    "            else:\n",
    "                return total, val \n",
    "        \n",
    "        total, val = DFS(0,-1)\n",
    "        #print(total, val)\n",
    "        if val==0:\n",
    "            return total\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        table = [set() for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            table[x].add(y)\n",
    "            table[y].add(x)\n",
    "\n",
    "        def dfs(node,pa):\n",
    "            nonlocal ans\n",
    "            sm = values[node]\n",
    "            for chil in table[node]:\n",
    "                if chil!=pa: # 路径只能是单向的，不允许从子节点再到父节点\n",
    "                    sm+=dfs(chil,node) #非python要注意每加一个就取模一次\n",
    "            if sm%k==0: # 这个节点为根的子树内部被删了多少次不用管（无论怎么删，剩下的部分也还是k的倍数），只要知道这个node和pa能断开就可以了\n",
    "                ans+=1\n",
    "            return sm\n",
    "        \n",
    "        dfs(0,-1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        adj = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "\n",
    "        vis = set()\n",
    "        def dfs(k_, i):\n",
    "            vis.add(i)\n",
    "            t, r = 0, values[i]\n",
    "            for j in adj[i]:\n",
    "                if j in vis: continue\n",
    "                t_, r_ = dfs(k_, j)\n",
    "                t += t_\n",
    "                r += r_\n",
    "            if r%k_ == 0:\n",
    "                t += 1\n",
    "                r = 0\n",
    "            return t, r\n",
    "        \n",
    "        ans, _ = dfs(k, 0)\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        dct = dict(zip(range(n), values))\n",
    "        ans = 0\n",
    "        \n",
    "        def f(x, fa):\n",
    "            nonlocal ans\n",
    "            s0 = dct[x]\n",
    " \n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    s = f(y, x)\n",
    "                    if s % k == 0: ans += 1\n",
    "                    else: s0 += s\n",
    "\n",
    "            return s0\n",
    "        f(0, -1)\n",
    "        return ans + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        adj = collections.defaultdict(set)\n",
    "        for a, b in edges:\n",
    "            adj[a].add(b)\n",
    "            adj[b].add(a)\n",
    "        seen = set()\n",
    "        ans = 0\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "            v = values[node]\n",
    "            for c in adj[node]:\n",
    "                adj[c].remove(node)\n",
    "                v += dfs(c)\n",
    "            if v % k == 0:\n",
    "                ans += 1\n",
    "                return 0\n",
    "            else:\n",
    "                return v\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "        ans = 0\n",
    "        \n",
    "        def dfs(x, fa):\n",
    "            nonlocal ans\n",
    "            res = values[x]\n",
    "            for y in g[x]:\n",
    "                if y == fa: continue\n",
    "                s = dfs(y, x)  # 子树和\n",
    "                if s % k == 0:\n",
    "                    ans += 1\n",
    "                    continue\n",
    "                res += s\n",
    "            return res\n",
    "        \n",
    "        if dfs(0, -1) % k == 0:\n",
    "            return ans + 1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        for i, v in enumerate(values):\n",
    "            values[i] %= k\n",
    "        visited = [0] * n\n",
    "        g = defaultdict(set)\n",
    "        for a, b, in edges:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        cnt_list = values.copy()\n",
    "        def DFS(x, fa):\n",
    "            nonlocal ans\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    DFS(y, x)\n",
    "                    if cnt_list[y] % k == 0:\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        cnt_list[x] += cnt_list[y]\n",
    "        ans = 1\n",
    "        DFS(0, -1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edg: List[List[int]], values: List[int], k: int) -> int:\n",
    "        edges={i:set() for i in range(n)}\n",
    "        for i in edg:\n",
    "            a,b=i[0],i[1]\n",
    "            edges[a].add(b)\n",
    "            edges[b].add(a)\n",
    "        ans=0\n",
    "        def dfs(node,pa):\n",
    "            nonlocal ans\n",
    "            csum=values[node]\n",
    "            for neighbor in edges[node]:\n",
    "                if neighbor!=pa:\n",
    "                    csum+=dfs(neighbor,node)\n",
    "            if csum%k==0:\n",
    "                ans+=1\n",
    "            return csum \n",
    "        dfs(0,-1)\n",
    "        return ans\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:\n",
    "        from collections import defaultdict\n",
    "        preSums = defaultdict(int)\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "\n",
    "        def getSums(node, fa):\n",
    "            nonlocal preSums, graph\n",
    "            the_sums = values[node]\n",
    "            for y in graph[node]:\n",
    "                if y == fa:\n",
    "                    continue\n",
    "                the_sums += getSums(y, node)\n",
    "\n",
    "            preSums[node] = the_sums\n",
    "            return the_sums\n",
    "        \n",
    "        _ = getSums(0, -1)\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        def getRes(node, fa):\n",
    "            nonlocal ans\n",
    "            for y in graph[node]:\n",
    "                if y == fa:\n",
    "                    continue\n",
    "                num, flag = getRes(y, node)\n",
    "                if flag:\n",
    "                    preSums[node] -= num\n",
    "            \n",
    "            if preSums[node] % k == 0:\n",
    "                ans += 1\n",
    "                return preSums[node], True\n",
    "            return -1, False\n",
    "\n",
    "        getRes(0, -1)\n",
    "\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
